package arithmetic.LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 210. 课程表 II
 * <p>
 * https://leetcode.cn/problems/course-schedule-ii/description/
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前
 * 必须 先选修 bi 。
 * <p>
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：[0,1]
 * 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
 * 示例 2：
 * <p>
 * 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
 * 输出：[0,2,1,3]
 * 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
 * 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
 * 示例 3：
 * <p>
 * 输入：numCourses = 1, prerequisites = []
 * 输出：[0]
 *
 * @author jiangfeng on 2024/1/4
 */
public class findOrder {
    public static void main(String[] args) {


        System.out.println(Arrays.toString(new Solution().findOrder(5, new int[][] {{1, 4}, {2, 4}, {3, 1}, {3, 2}})));
        //        System.out.println(new Solution().canFinish(3,new int[][]{{1,0},{1,2},{0,1}}));
        //        System.out.println(new Solution().canFinish(2,new int[][]{{1,0},{0,1}}));
        System.out.println(Arrays.toString(new Solution().findOrder(2, new int[][] {{1, 0}, {2, 0}, {0, 2}})));
        System.out.println(Arrays.toString(new Solution().findOrder(2,
                new int[][] {{1, 0}, {0, 3}, {0, 2}, {3, 2}, {2, 5}, {4, 5}, {5, 6}, {2, 4}})));
    }

    static class Solution {

        class PreCourses {
            List<Integer> courses = new ArrayList<>();
            boolean canFinish;
        }

        public int[] findOrder(int numCourses, int[][] prerequisites) {
            // 1 准备工作
            List<Integer> r = new ArrayList<>();
            Map<Integer, PreCourses> map = new HashMap<>();
            Set<Integer> s = new HashSet<>();
            for (int i = 0; i < prerequisites.length; i++) {
                s.add(prerequisites[i][0]);
                s.add(prerequisites[i][1]);
                PreCourses l = map.getOrDefault(prerequisites[i][0], new PreCourses());
                l.courses.add(prerequisites[i][1]);
                map.put(prerequisites[i][0], l);
            }

            // 2 计算有依赖的顺序
            Deque<Integer> dq = new ArrayDeque<>();
            for (int i = 0; i < prerequisites.length; i++) {
                if (isCycle(prerequisites[i][0], dq, map, r)) {
                    // 有环，返回空数组
                    return new int[0];
                }

            }

            // 3 结果添加：先加入有依赖的
            int[] result = new int[numCourses];
            for (int i = 0; i < r.size(); i++) {
                result[i] = r.get(i);
            }
            // 没有依赖的随便学
            int count = 0;
            int i = r.size();
            while (i < numCourses) {
                if (!s.contains(count)) {
                    result[i++] = count;
                }
                count++;
            }

            return result;
        }

        public boolean isCycle(Integer value, Deque<Integer> dq, Map<Integer, PreCourses> map, List<Integer> r) {
            PreCourses courses = map.get(value);
            if (courses == null) {
                //   没有前置课，或者已经有前置课但已经计算过能修 快速返回.
                if (!r.contains(value)) {
                    r.add(value);
                }

                return false;
            }
            if (courses.canFinish) {
                return false;
            }
            // 开始计算是否能修
            dq.push(value);
            for (Integer k : courses.courses) {
                //  该课已经在依赖路径里啦 有环直接否定
                if (dq.contains(k)) {
                    return true;
                }
                // 并列多个 前置条件，需要都满足
                if (isCycle(k, dq, map, r)) {
                    return true;
                }
            }
            // 全部满足了能修 标记一下，可以出栈
            courses.canFinish = true;
            r.add(dq.pop());
            return false;
        }

    }


    // 错误的

}
